package Array;

public class item53 {
//    定义dp[i] 为前i个元素的最大和为dp[i]
//    当dp[i-1]>0时，dp[i] = dp[i-1]+nums[i]
//    当dp[i-1]<=0时，dp[i] =nums[i]
    public int maxSubArray(int[] nums) {
        int max= 0;
        int start = 0;
        int [] dp =new int[nums.length];
        dp[0] = nums[0];
        for (int i = 1; i < nums.length ; i++) {
            if(dp[i-1]>0)
            {
                dp[i] = dp[i-1]+nums[i];
            }else
                dp[i] = nums[i];
            max = Math.max(dp[i],max);
        }
        return max;
    }
}
